﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * 

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

     * */
    class Problem133 : IProblem
    {
        public string Calculate()
        {
            long[] p = new long[100000];
            p[0] = 2;

            SieveOfAtkin sieve = new SieveOfAtkin(1000000);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
            }

            int limit = 100000;

            long sum = 0;

            for (int i = 0; i < p.Length && p[i] < limit; i++)
            {
                bool[] remainder = new bool[p[i]];

                long n = 0;
                int r = 0;
                while (true)
                {
                    r++;
                    n = n * 10 + 1;
                    n = n % p[i];

                    if (remainder[n])
                    {
                        sum += p[i];
                        //Console.WriteLine(p[i]);
                        break;
                    }
                    else
                    {
                        remainder[n] = true;
                        if (n == 0)
                        {
                            if (IsInfiniteDivision(10,r))
                            {
                                sum += p[i];
                                //Console.WriteLine(p[i]);
                            }
                            break;
                        }
                    }
                }

                //Console.ReadKey();
            }


            return sum.ToString();
        }

        bool IsInfiniteDivision(int a, int b)
        {
            HashSet<int> remainders = new HashSet<int>();
            int n = a;
            while (n > 0)
            {
                if (!remainders.Add(n))
                    return true;
                n %= b;
                n *= 10;
            }

            return false;
        }
    }
}
